import com.sun.deploy.uitoolkit.impl.fx.AppletStageManager;

public class Solution208 {
    /**
     * 实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
     * <p>
     * 示例:
     * <p>
     * Trie trie = new Trie();
     * <p>
     * trie.insert("apple");
     * trie.search("apple");   // 返回 true
     * trie.search("app");     // 返回 false
     * trie.startsWith("app"); // 返回 true
     * trie.insert("app");
     * trie.search("app");     // 返回 true
     */
    public static void main(String[] args) {
        Trie trie = new Solution208().new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple"));
        System.out.println(trie.search("app"));
        System.out.println(trie.startsWith("app"));
        trie.insert("app");
        System.out.println(trie.search("app"));
    }

    class Trie {
        private TrieNode root;

        /**
         * Initialize your data structure here.
         */
        public Trie() {
            root = new TrieNode();
        }

        /**
         * Inserts a word into the trie.
         */
        public void insert(String word) {
            if (word == null) {
                return;
            }
            TrieNode node = root;
            char[] array = word.toCharArray();
            for (char c : array) {
                if (node.nexts[c - 'a'] == null) {
                    node.nexts[c - 'a'] = new TrieNode();
                }
                node = node.nexts[c - 'a'];
                node.path++;
            }
            node.end++;
        }

        /**
         * Returns if the word is in the trie.
         */
        public boolean search(String word) {
            TrieNode node = root;
            char[] array = word.toCharArray();
            for (char c : array) {
                if (node.nexts[c - 'a'] == null) {
                    return false;
                }
                node = node.nexts[c - 'a'];
            }
            return node.end > 0;
        }

        /**
         * Returns if there is any word in the trie that starts with the given prefix.
         */
        public boolean startsWith(String prefix) {
            TrieNode node = root;
            char[] array = prefix.toCharArray();
            for (char c : array) {
                if (node.nexts[c - 'a'] == null) {
                    return false;
                }
                node = node.nexts[c - 'a'];
            }
            return true;
        }
    }

    class TrieNode {
        public int path;
        public int end;
        public TrieNode[] nexts;

        public TrieNode() {
            this.path = 0;
            this.end = 0;
            this.nexts = new TrieNode[26];
        }
    }
}
